package 递归回溯;

import java.util.HashMap;
import java.util.Map;

public class No494目标和 {

    /**
     * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。
     * 对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
     * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
     *
     * 示例：
     * 输入：nums: [1, 1, 1, 1, 1], S: 3
     * 输出：5
     * 解释：
     * -1+1+1+1+1 = 3
     * +1-1+1+1+1 = 3
     * +1+1-1+1+1 = 3
     * +1+1+1-1+1 = 3
     * +1+1+1+1-1 = 3
     * 一共有5种方法让最终目标和为3。
     */

    private int count=0;
    private int sum=0;
    private int[] arr;
    private Map<String,Integer> meme=new HashMap<>();

    public int findTargetSumWays(int[] nums, int S) {
        this.arr=nums;
        this.sum=S;
//        dg(0,0);
//        return count;
        return dgMemo(0,0);
    }

    //普通版本
    private void dg(int index,int sum){
        //遍历完毕,查看和是否为0
        if(index==arr.length){
            System.out.println("终点和:"+sum);
            //最后一步未加减
            if(sum==this.sum) {
                count++;
            }
            return;
        }
        //开始遍历
        dg(index+1,sum+arr[index]);
        dg(index+1,sum-arr[index]);
    }

    //备忘录版本
    private int dgMemo(int index,int sum){
        //遍历完毕,查看和是否为0
        int count=0;
        if(index==arr.length){
//            System.out.println("终点和:"+sum);
            if(sum==this.sum) {
                return 1;
            }
            return 0;
        }
        Integer memo = meme.get(index+","+sum);
        if(memo!=null){
            return memo;
        }
        count+=dgMemo(index+1,sum+arr[index]);
        count+=dgMemo(index+1,sum-arr[index]);
        meme.put(index+","+sum,count);//""+index+sum这样放可能会相同,例如:index=1 sum=123;index=11 sum=23
        return count;
    }

    //动态规划版本

    /**
     * 利用动态规划求解,求前i个元素组成值j的方案个数
     * i:[0..nums.length-1] j:[-S..0..S]
     * f(i,j)=f(i-1,j-arr[i])+f(i-1,j+arr[i])
     */
    public int findTargetSumWaysDp(int[] nums,int S){

        //题目给了数组最大和为1000,我们区分+1000和-1000
        int[][] dp=new int[nums.length][2001];

        //根据自己的图,先把第一排搞定
        dp[0][nums[0]+1000]=1;
        //这里细节,如果第一个值是0的话,需要i+=1;不然会覆盖
        dp[0][-nums[0]+1000]+=1;


        for (int i = 1; i < nums.length; i++) {
            for (int j = -1000; j <= 1000; j++) {
//                if (dp[i - 1][j + 1000] > 0) {//才不会越界
                    //检测上一排是否有值,有值则对当前下标左右两侧进行相加
                    System.out.println(i+","+(j + arr[i] + 1000));
                    if((j + arr[i] + 1000)<=2000) {
                    dp[i][j + arr[i] + 1000] = dp[i][j + arr[i] + 1000] + dp[i - 1][j + 1000];
                    }
                    System.out.println(i+","+(j - arr[i] + 1000));
                    if((j - arr[i] + 1000)>=0) {
                    dp[i][j - arr[i] + 1000] = dp[i][j - arr[i] + 1000] + dp[i - 1][j + 1000];
                    }
//                }
            }
        }

        //S>1000根据题意意思
        return S>1000?0:dp[nums.length - 1][S + 1000];
    }

    public static void main(String[] args) {
        No494目标和 n=new No494目标和();
        int[] arr=new int[]{0,0,0,0,0,0,0,0,1};
        int result = n.findTargetSumWays(arr, 1);
        System.out.println(result);
        int result2=n.findTargetSumWaysDp(arr,1);
        System.out.println(result2);
    }

}
